package com.leetcode;

import com.leetcode.common.ListNode;

import static com.leetcode.util.LinkedListUtil.*;

/**
 * 92. 反转链表 II
 * 穿针引线
 *
 * @author fy
 * @date 2022/4/9 15:08
 */
public class Solution92 {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyHead = new ListNode(-1, head);

        ListNode cur = dummyHead;
        for (int i = 0; i < left - 1; i++) {
            cur = cur.next;
        }
        ListNode pre = cur;

        ListNode leftNode = pre.next;
        for (int i = 0; i < right - left + 1; i++) {
            cur = cur.next;
        }

        ListNode rightNode = cur;
        cur = cur.next;

        pre.next = null;
        rightNode.next = null;

        reverseList(leftNode);

        pre.next = rightNode;
        leftNode.next = cur;

        return dummyHead.next;
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;

            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5};
        ListNode head = createList(nums);
        int left = 2;
        int right = 4;
//        int[] nums = new int[]{5};
//        ListNode head = createList(nums);
//        int left = 1;
//        int right = 1;

        ListNode newHead = new Solution92().reverseBetween(head, left, right);
        printList(newHead);
    }

}
